The present invention relates to buffering data in a computer system.
A computer system has limited memory for storing data processed by the computer system. At any given time, the amount of data to be processed may exceed the amount that may be stored in volatile memory. To address this problem, buffering systems are used. Generally, buffering systems use an area of volatile memory to store a portion of the data to be processed. This area of memory is referred to as a cache. Whenever a computer system needs a subset of data, it retrieves the needed subset from the cache. If the cache does not hold the data, then the computer system retrieves the data from the storage area holding the needed data (e.g. a non-volatile storage device, or another area of volatile memory), then may store the retrieved data in the cache. Over time, the cache becomes fill. When the cache is full, and a computer system needs data that is not in the cache, the computer system replaces a subset of data currently residing in the cache with the needed data. If the replaced data has been changed while it resided in the cache , it is typically written to another storage area (e.g. non-volatile storage device) before it is replaced.
The process of replacing a subset of data in a cache with another subset of data from another storage area, and then storing the replaced subset of data in area other than the cache, is referred to as swapping. Excessive swapping can be expensive, especially for caches used to buffer data between disk storage and volatile memory.
To reduce swapping, many buffering approaches have been developed. Typically, the goal of these buffering approaches is to retain in cache data that will reduce swapping, and to replace data whose absence will least increase swapping. The degree to which a set of data tends to reduce swapping if retained in memory is referred to as the profit of the set of data.
Each buffering approach uses some measure to gauge profit. Measures of profit are typically based on access characteristics that reflect the history of access to a set of data. These historical access characteristics are used to estimate the degree to which the data is likely to be accessed in the near future. Data that has access characteristics that indicates that it will be the least likely to be accessed (i.e. low profit) is replaced from the cache, data with access characteristics that indicate that it will be the most likely to be accessed (i.e. high profit) is retained.
Conventional buffering approaches include the least recently used (LRU) approach, the least frequently used (LFU) approach, and the first-in first-out (FIFO) approach. The LRU approach replaces the least recently used data in the cache with new data. Thus, under the LRU approach, the data with the highest profit is the most recently used data. The LRU approach is based on xe2x80x9clocality of reference,xe2x80x9d the tendency in computer programs to access within a period of time the same subsets of data. Thus, the data that was the most recently accessed is the data that will most likely be accessed in the near future.
The LFU approach replaces the least frequently used data. Thus, under the LFU approach, the data with the highest profit is the most frequently used data. The FIFO approach replaces the oldest data. Under the FIFO approach, the data with the highest profit is the newest data added to the cache.
A wide range of applications, especially in the operating system and database systems, use an ordered LRU list. A common LRU list implementation is an ordered linked list of buffers. The order of the list is important because it reflects the order in which the buffers are selected for replacement. The order is thus referred to as the replacement order. The replacement order reflects the profit of buffers relative to each other, as measured by recency of use. The buffer at the top of the list contains the most recently used data. The buffer at the bottom of the list contains the least recently used data. When a given buffer is accessed, the buffer is moved to the top of the list. When new data is brought into the cache, it replaces data in the buffer at the bottom of list (least recently used buffer). The buffer is then moved to the top of the list.
One disadvantage of the LRU approach is that a considerable amount of overhead is required to rearrange the list each time a buffer""s data is accessed. Because of locality of reference, buffers at the top of list are the most likely to be accessed again in the near future. Consequently, many buffers at the top of the list do not progress very far toward the bottom before they are moved back to the top. Thus, much work is often wasted juggling buffers that remain near the top anyway.
Another disadvantage of the LRU approach is that it uses only one characteristic that indicates profit and ignores other highly relevant ones. As a result, a buffer which is in fact associated with the lowest profit among all buffers may be placed at top of the list. The replacement order thus inaccurately reflects the order of the true profit. For example, an LRU list contains buffers which are all being frequently accessed, except for a first buffer. When the first buffer is accessed, it is moved to the top of the list, above buffers which in fact have much higher profit.
A conventional buffering approach which does account for multiple characteristics that indicate profit is the buffering approach developed by Robinson and Murthy, herein referred to as the xe2x80x9cRobinson approachxe2x80x9d. The Robinson approach is an extension of the LRU approach. Like the LRU approach, in the Robinson approach buffers are maintained in an ordered link list, and the most recently used buffers are moved to the top of the list. However, when selecting a buffer for replacement, Robinson measures profit by accounting for, in addition to recency of use, frequency of access. Specifically, for each buffer a touch count is maintained. The touch count reflects the number of times a buffer has been accessed. When a buffer is selected for replacement, a subset of the buffers at the bottom of the list are examined. The buffer with the lowest touch count in the subset is selected for replacement.
One disadvantage of the Robinson approach is that the order of the list of buffers does not actually reflect a measure of profit that accounts for both recency of use and frequency of use. The reason for this lack of accounting is that the Robinson measure of profit is inconsistently calculated. Frequency of access is considered only when selecting a replacement. However, when a buffer is accessed, it is moved to the top of the list regardless of its touch count. Moreover, while the buffer list could be reordered using a consistent measure of profit, such a reordering is an expensive operation, and may negate any gain.
Based on the foregoing, it is clearly desirable to provide a method for measuring profit that accounts for multiple characteristics relevant to profit, and that efficiently selects data for replacement based on a consistently applied measure of profit.
A method and apparatus for buffering data is described. According to an aspect of the present invention, a set of buffers is maintained in an ordered list based on a profit value generated for each buffer. The profit value for a buffer reflects multiple access characteristics of the buffer. The list of buffers is partitioned into divisions referred to as buckets. Each bucket contains a set of buffers and is associated with a subrange of the full range of profit values that may be generated. The bucket that covers the very top of the list is associated with highest profit value subrange, the bucket that covers the bottom of the list is associated with the lowest profit value subrange.
According to another aspect of the present invention, when data is first placed in a buffer, the buffer""s position within the buffer list is not immediately based on its profit value. Instead, an access history is first accumulated for the buffer and, once accumulated, the buffer""s profit value earns the buffer""s place in the list. Specifically, after new data is added to a buffer, it is placed at the insertion point for the list. When the buffer is next accessed, it is placed at the top of list. As other buffers are added to the top of the list above the buffer, the buffer is pushed down the list. While the buffer is being pushed down the list, it is referenced, its access history is updated, but its order within the list is left unchanged, until the buffer crosses a certain position within the list. After the buffer crosses this position, the buffer""s profit value dictates the buffer""s place in the list.
According to another aspect of the present invention, a buffer""s profit value is a function of multiple access characteristics. Specifically, one or more profit factors that each reflect one or more access characteristics are used to generate the profit values. Examples of profit factors include, but are not limited to, normalized values that reflect (1) a buffer""s relative frequency of access (i.e. relative to other buffers in the cache), (2) a buffer""s relative recency of access, (3) the relative tenure of data currently residing in a buffer, or (4) the relative frequency of access within a subset of accesses to any buffers in the cache. In calculating a profit value for a buffer, the profit factors may be accorded equal weight, or accorded weight by application of any desired function.